// 中序遍历，左中右

// 思路1：递归

function inorderTraversal(root) {
    let result = []
    function dfs(root) {
        if (!root) {
            return
        }
        dfs(root.left)
        result.push(root.val)
        dfs(root.right)
    }
    dfs(root)
    return result
}

function inorderTraversal2(root) {
    let result = []
    let stack = []
    let cur = root
    while (stack.length || cur) {
        if (cur) {
            stack.push(cur)
            cur = cur.left
        } else {
            let node = stack.pop()
            result.push(node.val)
            cur = node.right
        }
    }
    return result
}

function inorderTraversal3(root) {
    let stack = [root]
    let result = []
    while (stack.length) {
        let node = stack.pop()
        if (!node) {
            result.push(stack.pop().val)
            continue
        }
        if (node.right) {
            stack.push(node.right)
        }
        stack.push(node)
        stack.push(null)
        if (node.left) {
            stack.push(node.left)
        }
    }
    return result
}

const root = {
    val: "A",
    left: {
        val: "B",
        left: {
            val: "D",
        },
        right: {
            val: "E",
        },
    },
    right: {
        val: "C",
        right: {
            val: "F",
        },
    },
};

console.log(inorderTraversal(root))
console.log(inorderTraversal2(root))
console.log(inorderTraversal3(root))